package done.easy_101_200;

import com.study.common.ListNode;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 160. Intersection of Two Linked Lists 相交链表
 * <p>
 * 编写一个程序，找到两个单链表相交的起始节点。
 * 如下面的两个链表,在节点 c1 开始相交:
 * <p>
 * 示例 1：（注意虽然两个链表都有 1 ，但是两个 1 是不同的对象，这里要求对象都一样）
 * 4 -> 1
 * -> 8 -> 4 -> 5
 * 5 -> 0 -> 1
 * <p>
 * 输入：
 * intersectVal = 8,
 * listA = [4, 1, 8, 4, 5],
 * listB = [5, 0, 1, 8, 4, 5],
 * skipA = 2,
 * skipB = 3
 * 输出：Reference of the node with value = 8
 * 解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。
 * 从各自的表头开始算起，
 * 链表 A 为 [4, 1, 8, 4, 5]，
 * 链表 B 为 [5, 0, 1, 8, 4, 5]。
 * 在 A 中，相交节点前有 2 个节点；
 * 在 B 中，相交节点前有 3 个节点。
 * <p>
 * 2019-04-11 11:26 PM
 **/
@SuppressWarnings("all")
public class IntersectionOfTwoLinkedLists {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 190411 first
        // 190529 second 看答案做出来的
        // 190605 third
        return null;
    }

    @Test
    public void test() {
        // 链表的公共部分
        ListNode eight = new ListNode(8, 4, 5);

        // 列表A
        ListNode headA = new ListNode(4, 1);
        headA.next = eight;

        // 列表B
        ListNode headB = new ListNode(5, 0, 1);
        headB.next = eight;

        info(getIntersectionNode(headA, headB));
    }
}








































/*
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部,
    // 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
    // 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
    if(headA == null || headB == null)
        return null;

    ListNode pA = headA;
    ListNode pB = headB;

    // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头,
    // 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
    while(pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}
*/
